#include "common.h"
namespace common {
int maximumProductOpt(std::vector<int> &nums) {
    std::sort(nums.begin(), nums.end());
    const int n = nums.size();
    return std::max(nums[n - 1] * nums[n - 2] * nums[n - 3],
                    nums[0] * nums[1] * nums[n - 1]);
}
int maximumProduct(std::vector<int> &nums) {
    int large[3] = {std::numeric_limits<int>::min(),
                    std::numeric_limits<int>::min(),
                    std::numeric_limits<int>::min()};
    int min[2] = {std::numeric_limits<int>::max(),
                  std::numeric_limits<int>::max()};
    for (auto n : nums) {
        if (n < min[0]) {
            min[1] = min[0];
            min[0] = n;
        } else if (n < min[1]) {
            min[1] = n;
        }
        if (n > large[2]) {
            // 一旦有更大值则移位
            large[0] = large[1];
            large[1] = large[2];
            large[2] = n;
        } else if (n > large[1]) {
            large[0] = large[1];
            large[1] = n;
        } else if (n > large[0]) {
            large[0] = n;
        }
    }
    return std::max(min[0] * min[1] * large[2], large[0] * large[1] * large[2]);
}
} // namespace common
